def find_common(root, p, q):
    def covers(root, node):
        if root == node:
            return True
        if not root:
            return False
        return covers(root.left, node) or covers(root.right, node)

    # p、q缺失
    if not covers(root, p) or not covers(root, q):
        return None

    # 递归终止条件
    if (not root) or (root == p) or (root == q):
        return root
    p_is_onleft = covers(root.left, p)
    q_is_onleft = covers(root.left, q)

    # p、q不在一边
    if p_is_onleft != q_is_onleft:
        return root

    # 递归调用
    side = root.left if p_is_onleft else root.right
    return find_common(side, p, q)


from instance import Tree1
ans = find_common(Tree1.tree1, Tree1.tree1.left.right, Tree1.tree1.right.left)
print(ans.val)
